package day_2022_9_to_12.Day;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/11/17 22:20
 **/
public class Day73_Review {
    class Solution {
        public int maxSubArray(int[] nums) {
            int max = nums[0];
            for(int i = 1; i < nums.length; ++i) {
                nums[i] = Math.max(nums[i-1] + nums[i], nums[i]);
                max = Math.max(max, nums[i]);
            }
            return max;
        }
    }

    class Solution2 {
        ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode node1 = headA;
            ListNode node2 = headB;
            while(node1 != node2) {
                node1 = node1 == null ? headB : node1.next;
                node2 = node2 == null ? headA : node2.next;
            }
            return node1;
        }
    }

    class Solution3 {
        public int search(int[] nums, int target) {
            int l = 0, r = nums.length, mid;
            while(l < r) {
                mid = l + ((r-l) >> 1);
                if(nums[mid] >= target) r = mid;
                else l = mid + 1;
            }
            int count = 0;
            while(l < nums.length && nums[l++] == target) count++;
            return count;
        }
    }

    class Solution4 {
        public int kthLargest(TreeNode root, int k) {
            Deque<TreeNode> s = new LinkedList<>();
            while(!s.isEmpty() || root != null) {
                while(root != null) {
                    s.push(root);
                    root = root.right;
                }
                root = s.pop();
                if(--k == 0) return root.val;
                root = root.left;
            }
            return -1;
        }
    }

    class Solution5 {
        public int maxDepth(TreeNode root) {
            if(root == null) return 0;
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        }
    }

    class Solution6 {
        public boolean isBalanced(TreeNode root) {
            if(root == null) return true;
            int l = getDep(root.left);
            int r = getDep(root.right);
            return Math.abs(l - r) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
        private int getDep(TreeNode cur) {
            if(cur == null) return 0;
            return 1 + Math.max(getDep(cur.left), getDep(cur.right));
        }
    }

    class Solution7 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == p || root == q) return root;
            if(root.val > p.val && root.val > q.val) {
                return lowestCommonAncestor(root.left, p, q);
            }else if(root.val < p.val && root.val < q.val) {
                return lowestCommonAncestor(root.right, p, q);
            }else return root;
        }
    }

    class Solution8 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) return null;
            if(root == p || root == q) return root;
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            if(l != null && r != null) return root;
            if(l != null) return l;
            else return r;
        }
    }

    class Solution9 {
        public int add(int a, int b) {
            while(b != 0) {
                int carry = (a & b) << 1;
                a = a ^ b;
                b = carry;
            }
            return a;
        }
    }

}